package Labirinto;

import java.util.Vector;
import Labirinto.*;

/**
 * A classe Busca implementa os algoritmos para busca em espa�o de estados. Ela
 * mant�m a estrutura de �rvore na qual s�o feitas as infer�ncias sobre os nodos.
 */
public class Busca{
    
    Labirinto labirinto;
    Nodo raiz;
    boolean debug;
    int custo;

    /**
     * Construtor do algoritmo de busca. Mant�m uma refer�ncia para a 
     * implementa��o do labirinto (o problema), a raiz da �revore de estados e a
     * flag para debug.
     *
     * @param l refer�ncia para a implementa��o do labirinto.
     * @param d ativa(true)/desativa(false) o debug.
     */
    public Busca(Labirinto l, boolean d){
	labirinto = l; 
	raiz = new Nodo(null, labirinto.getPosicaoAtual());
	debug = d;
    }

    /**
     * Executa busca pelo m�todo selecionado.  
     * 
     * @param aEstrela Flag para o tipo de busca selecionado. Com informa��o
     * heur�stica e custo (A*) ou somente heur�stica (guloso)
     */
    public Posicao[] buscar(boolean aEstrela, boolean aEstrelaAlt){

	Nodo nodoSolucao = this.expandir(raiz, aEstrela, aEstrelaAlt);

	if (nodoSolucao != null){
	    if (debug) System.out.println("\n Solu��o encontrada com " + nodoSolucao.getProfundidade() + " passos.");

	    Posicao solucao[] = new Posicao[nodoSolucao.getProfundidade() + 1 ];
	    int c = 0;
	    do{
		solucao[c] = (Posicao)nodoSolucao.getValor();
		c++;
		//setcusto(c);
		nodoSolucao = nodoSolucao.getPai();
		//  } while (!((Posicao)nodoSolucao.getValor()).comparaCom((Posicao)raiz.getValor()));
	    } while ( nodoSolucao != null );
	    return solucao;
	} else {
	    if (debug) System.out.println("[BUSCADOR] Solu��o n�o encontrada.");
	    return null;
	}
    }

    /**
     * Expande recursivamene o espa�o de estados atual com base no crit�rio de 
     * busca. Devolve uma rever�ncia para nodo solu��o encontrado no espa�o de
     * estados.
     *
     * @param n nodo que deve ser expandido.
     * @param aEstrela Flag para o tipo de busca selecionado. Com informa��o
     * heur�stica e custo (A*) ou somente heur�stica (guloso)
     * @return devolve uma refer�ncia para nodo solu��o encontrado no espa�o de
     * estados.
     */
    public Nodo expandir(Nodo n, boolean aEstrela, boolean aEstrelaAlt){

	if ( n.getProfundidade() > (2 * labirinto.getDimX() * labirinto.getDimY()) ) { // Profundidade maior que o n�mero de posi��es poss�veis
	    if (debug) System.out.println("\n Parando por exaust�o de passos (" + n.getProfundidade() + ").");
	    return null;
	}
	else {
	    
	    Posicao p = (Posicao)n.getValor();
	    Vector<Posicao> exp = labirinto.getExpansao(p);
	    if (debug)
		System.out.println("Expandindo posi��o " + p.toString());
	    
	    Nodo novoFilho;
	    Nodo candidato = null;
	    Nodo anterior  = null;
	    double fN;
	    double minFN   = (labirinto.getDimX() * labirinto.getDimX()) + (labirinto.getDimY() * labirinto.getDimY());
	    double gAMV    = 0;
	    double hDLR;
	    
	    for (int c=0; c<exp.size(); c++){
		if (labirinto.getValorPosicao(exp.elementAt(c)) == 0 || 
		    labirinto.getValorPosicao(exp.elementAt(c)) == 2 || 
		    labirinto.getValorPosicao(exp.elementAt(c)) == 3) {
		    novoFilho = new Nodo(n,exp.elementAt(c));
		    n.setFilho(novoFilho);
		    setcusto(getCusto()+1);
		    fN   = 0;
		    gAMV = 0;
		    hDLR = labirinto.getDLR(exp.elementAt(c), labirinto.getPosicaoSaida()); // Heur�stica
		    
		    if (aEstrela && n.getPai() != null) { // usar A* e evitar o nodo raiz
                        if (aEstrelaAlt)
                            gAMV = Math.pow(2,this.getAscendenteAlt(novoFilho, novoFilho.getPai(),0)); // Custo
                        else
                            gAMV = this.getAscendente(novoFilho, novoFilho.getPai(),0); // Custo
			fN = gAMV + hDLR;
		    } else
			fN = hDLR;
		    if (fN < minFN) {
			candidato = novoFilho;
			minFN = fN;
		    }
		    if (debug) {
			System.out.print("\tFilho " + ((Posicao)novoFilho.getValor()).toString() + "\t f(n)=" + fN + "\t h(n)=" + hDLR);
			if (aEstrela) System.out.print("\t g(n)=" + gAMV);
			
			System.out.println();
		    }  
		}
	    }
	    if ( candidato == null ) // Ponto de entrada preso entre obst�culos
		return null;
	    else {
		if (((Posicao)candidato.getValor()).comparaCom(labirinto.getPosicaoSaida()))
		    return candidato; // Encontrou uma solu��o
		else {
		    if ( !aEstrela ) {
			Nodo pai = n.getPai();	    
			if (pai != null && ((Posicao)pai.getValor()).comparaCom((Posicao)candidato.getValor())) {
//			    System.out.println("\n ATEN��O: Sem solu��o");
			    return candidato; // N�o encontrou a solu��o e para por n�o ser A*
			}
			else		
			    return expandir(candidato, aEstrela, aEstrelaAlt); // Continua procurando
		    } else
			return expandir(candidato, aEstrela, aEstrelaAlt); // Continua procurando
		}
	    }
	}
    }
    
    /**
     * Contabiliza a quantidade de vezes que se visitou uma dada posi��o
     * pesquisando a posi��o na �rvore do espa�o de estados. � uma fun��o
     * recursiva que segue do nodo fornecido inicialmente at� a raiz do espa�o
     * de estados.
     *
     * @param folha Nodo que est� sendo pesquisado na �rvore.
     * @param atual Nodo que est� sendo verificado neste itera��o.
     * @param custo Custo acumulado at� esta itera��o. Custo de cada encontro �
     * 1.
     */
    private int getAscendente(Nodo folha, Nodo atual, int custo){
    	setcusto(getCusto()+1);
	if ( atual != null)
	    if (((Posicao)folha.getValor()).comparaCom((Posicao)atual.getValor()))
		return getAscendente(folha, atual.getPai(), custo + 1); // Encontrou um parente
	    else 
		return getAscendente(folha, atual.getPai(), custo); // Continua procurando
	else
	    return custo;
    }

    private double getAscendenteAlt(Nodo folha, Nodo atual, double custo){
    	setcusto(getCusto()+1);
	if ( atual != null)
	    if (((Posicao)folha.getValor()).comparaCom((Posicao)atual.getValor()))
		return getAscendenteAlt(folha, atual.getPai(), custo + 1); // Encontrou um parente
	    else
		return getAscendenteAlt(folha, atual.getPai(), custo); // Continua procurando
	else
	    return custo;
    }

    public void setLabirinto(Labirinto labirinto) {
        this.labirinto = labirinto;
	raiz = new Nodo(null, labirinto.getPosicaoAtual());
	custo = 0;
    }
    
    public int getCusto(){
    	return custo;
    }
    
    public void setcusto(int n){
    	custo =n;
    }
    
}